A storage device normally performs error correction coding on data to be stored therein in order to protect the data. A Maximum Likelihood Decoding (MLD) is a method of decoding a codeword that is error correction coded, the method using a received word to find, from a whole set of codewords, a decoded word with the maximum likelihood that is a codeword having the highest probability to be the one from which the received word is generated. The MLD involves a large amount of computation, however. Therefore, a near MLD is used in some cases to find, not from the whole set of codewords but from a subset of codewords, the codeword having the highest probability to be the one from which the received word is generated.